5/*
 * @lc app=leetcode.cn id=564 lang=cpp
 *
 * [564] 寻找最近的回文数
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>

using namespace std;
// @lc code=start
class Solution {
public:
     string nearestPalindromic(string n) {
        long long ori = stoll(n); // 保存原本的数值大小
        int i = 0, j = n.size() - 1;
        bool flag = true; // 判断本身是否是回文序列
        while(i < j){
            if(n[j] != n[i]){
                n[j] = n[i];
                flag = false;
            }
            ++i; --j;
        }
        map<long long, string> mp; // 用map自动排序，这里偷个懒...（注意优先级高的覆盖低的）
        string add = change(n, 1);
        string sub = change(n, -1);
        mp[abs(stoll(add) - ori)] = add;
        if(!flag) mp[abs(stoll(n) - ori)] = n; // 只有原本不是回文串才存入
        mp[abs(stoll(sub) - ori)] = sub;
        return mp.begin()->second;
    }
    string change(string n, long long x){
        string oldPre = n.substr(0, (n.size() + 1) / 2);
        string newPre = to_string(stoll(oldPre) + x);
        if(newPre.size() == 1 && newPre[0] == '0') newPre.pop_back(); // 规定0的位数小于1
        if(newPre.size() == oldPre.size()){ // 位数相等根据传入字符串的长度奇偶性返回答案
            string temp = newPre;
            reverse(temp.begin(), temp.end());
            if(n.size() % 2){
                return newPre + temp.substr(1);
            } else return newPre + temp;
        }
        else if(newPre.size() < oldPre.size()){ // 更改后位数减少了，返回"99..99"
            string ans = string(n.size() - 1, '9');
            if(ans.empty()) ans = "0";
            return ans;
        } else { // 更改后位数增加了，返回"100...001"
            string ans = string(n.size() + 1, '0');
            ans[0] = ans.back() = '1';
            return ans;
        }
    }
};
// @lc code=end


/**
         string nearestPalindromic(string n) {
        //三种特殊情况 9 -> 8, 10 -> 9,11-> 9, 99 -> 101
        if(stoi(n) <= 10 || stoi(n) == pow(10,(n.length()-1))) {
            int a = stoi(n)-1;
            return to_string(a);
        }
        if(stoi(n) == pow(10,(n.length()-1))+1) {
            int a = stoi(n)-2;
            return to_string(a);
        }
        if(stoi(n) == pow(10,(n.length()))-1) {
            int a = stoi(n)+2;
            return to_string(a);
        }
        string ret;
        string tmp = n;
        int half = n.length()/2;
        ret = n.substr(0,half);
        if(n.length() % 2 == 1) {
            ret.push_back(n[half]);
        }
        //判断该数是否已经是回文数
        reverse(tmp.begin(),tmp.end());
        if(tmp == n) {
            int a = ret[ret.length() - 1] - '0';
            a = a  == 0?a + 1:a - 1;
            ret[ret.length() - 1] = a + '0';
        }
        tmp = ret.substr(0,half);
        reverse(tmp.begin(),tmp.end());
        string ans = ret + tmp;

        if(ans > n) {

        }

        return ret;
        
    }
  
 */

